Afin de permettre à l'algorithme de prendre en compte un coût additionnel pour chaque ville qui sert d'étape intermédiaire, il faut commencer par implémenter une méthode qui calcule le coût total du trajet entre 2 villes (c-à-d en prenant en compte le nombre d'étapes/transits).

Ensuite, dans l'algorithme de Kruskal, 
après avoir retiré l'EdgeMin de la liste de priorité, il faut ajouter une condition qui vérifie que si les 2 villes sont dans le même ensemble et que le coût total les reliant est supérieur au poids de la liaison directe, alors on ajoute l'arête au graphe que l'on est en train de construire.

Cet algorithme modifié garanti toujours de produire une solution optimale car la modification n'altère pas les propriétés de l'algorithme de Kruskal de base, elle fournit des chemins supplémentaires meilleurs si nécessaire.